package com.wtgroup.demo.mianshi.算法.并查集;

import java.util.ArrayList;

/**
 * @author nisus
 * @version 0.1
 * @since 2023/5/5 11:04
 */
public class D2 {

    // 输入是数组格式
    public static class UnionSet<T> {
        T[] nodes; // 用户输入
        int[] parents; // parents[i]=j, nodes[i] 的 parent 是 nodes[j]
        int[] sizes; // sizes[i]=10, i 为root的集合有 10个. 不是root位置的值不影响放那就行, Map 结构的话, 非root的删掉

        public UnionSet(T[] values) {
            nodes = values;
            for (int i = 0; i < values.length; i++) {
                parents[i] = i; // 一开始各自的 parent 指向自身
                sizes[i] = 1; // 初始只有自己1个
            }
        }

        public boolean isSameSet(int i, int j) {
            // return loopFindRoot(i) == loopFindRoot(j)

            return false;
        }

        private int findRoot_complex(int i) {
            int curr = i;
            while (parents[curr] != curr) {
                curr = parents[curr];
            }
            return curr;
        }

        // 找代表节点
        int findRoot_recur(int i) {
            if (parents[i] == i) {
                return i;
            }
            int root = findRoot_recur(parents[i]);
            parents[i] = root;
            return root;
        }

        int findRoot_loop(int i) {
            ArrayList<Integer> path = new ArrayList<>();
            int curr = i;
            int ret = curr;
            while (parents[curr] != curr) {
                curr = parents[curr];
                path.add(curr);
            }
            for (Integer p : path) {
                parents[p] = ret;
            }
            return ret;
        }

        private int findRoot(int i) {
            return findRoot_complex(i);
        }

        public void union(int i, int j) {
            int iroot = findRoot(i);
            int jroot = findRoot(j);
            if (iroot == jroot) {
                return;// 已经是连通的
            }

            // 小的挂到大的下
            int small = sizes[iroot] < sizes[jroot] ? iroot : jroot;
            int big = small == iroot ? jroot : iroot;

            parents[small] = big;
            sizes[big] = sizes[small] + sizes[big];
        }

    }

}
